Search Results

Documents authored by Bousquet, Nicolas

Document
DOI: 10.4230/LIPIcs.STACS.2024.21
Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters

Authors: Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. For many classic global properties, like checking the acyclicity of the network, the optimal size of the certificates depends on the size of the network, n. In this paper, we focus on properties for which the size of the certificates does not depend on n but on other parameters. We focus on three such important properties and prove tight bounds for all of them. Namely, we prove that the optimal certification size is: Θ(log k) for k-colorability (and even exactly ⌈ log k ⌉ bits in the anonymous model while previous works had only proved a 2-bit lower bound); (1/2)log t+o(log t) for dominating sets at distance t (an unexpected and tighter-than-usual bound) ; and Θ(log Δ) for perfect matching in graphs of maximum degree Δ (the first non-trivial bound parameterized by Δ). We also prove some surprising upper bounds, for example, certifying the existence of a perfect matching in a planar graph can be done with only two bits. In addition, we explore various specific cases for these properties, in particular improving our understanding of the trade-off between locality of the verification and certificate size.
Cite as

Nicolas Bousquet, Laurent Feuilloley, and Sébastien Zeitoun. Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2024.21,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Zeitoun, S\'{e}bastien},
  title =	{{Local Certification of Local Properties: Tight Bounds, Trade-Offs and New Parameters}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.21},
  URN =		{urn:nbn:de:0030-drops-197317},
  doi =		{10.4230/LIPIcs.STACS.2024.21},
  annote =	{Keywords: Local certification, local properties, proof-labeling schemes, locally checkable proofs, optimal certification size, colorability, dominating set, perfect matching, fault-tolerance, graph structure}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.15
Galactic Token Sliding

Authors: Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Given a graph G and two independent sets I_s and I_t of size k, the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets (each of size k) I_s = I₀, I₁, I₂, …, I_𝓁 = I_t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G, the two most studied reconfiguration steps are token jumping and token sliding. In the Token Jumping variant of the problem, a single step allows a token to jump from one vertex to any other vertex in the graph. In the Token Sliding variant, a token is only allowed to slide from a vertex to one of its neighbors. Like the Independent Set problem, both of the aforementioned problems are known to be W[1]-hard on general graphs (for parameter k). A very fruitful line of research [Bodlaender, 1988; Grohe et al., 2017; Telle and Villanger, 2019; Pilipczuk and Siebertz, 2021] has showed that the Independent Set problem becomes fixed-parameter tractable when restricted to sparse graph classes, such as planar, bounded treewidth, nowhere-dense, and all the way to biclique-free graphs. Over a series of papers, the same was shown to hold for the Token Jumping problem [Ito et al., 2014; Lokshtanov et al., 2018; Siebertz, 2018; Bousquet et al., 2017]. As for the Token Sliding problem, which is mentioned in most of these papers, almost nothing is known beyond the fact that the problem is polynomial-time solvable on trees [Demaine et al., 2015] and interval graphs [Marthe Bonamy and Nicolas Bousquet, 2017]. We remedy this situation by introducing a new model for the reconfiguration of independent sets, which we call galactic reconfiguration. Using this new model, we show that (standard) Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. We believe that the galactic reconfiguration model is of independent interest and could potentially help in resolving the remaining open questions concerning the (parameterized) complexity of Token Sliding.
Cite as

Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad. Galactic Token Sliding. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.ESA.2022.15,
  author =	{Bartier, Valentin and Bousquet, Nicolas and Mouawad, Amer E.},
  title =	{{Galactic Token Sliding}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.15},
  URN =		{urn:nbn:de:0030-drops-169535},
  doi =		{10.4230/LIPIcs.ESA.2022.15},
  annote =	{Keywords: reconfiguration, independent set, galactic reconfiguration, sparse graphs, token sliding, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.15
Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint

Authors: Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.
Cite as

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2022.15,
  author =	{Bousquet, Nicolas and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and Ouvrard, Paul and Suzuki, Akira and Wasa, Kunihiro},
  title =	{{Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{15:1--15:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.15},
  URN =		{urn:nbn:de:0030-drops-158253},
  doi =		{10.4230/LIPIcs.STACS.2022.15},
  annote =	{Keywords: combinatorial reconfiguration, spanning trees, PSPACE, polynomial-time algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.19
Distributed Recoloring of Interval and Chordal Graphs

Authors: Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the study of this problem has been extended in two directions. First, the problem of recoloring, that is computing an efficient transformation between two given colorings (instead of computing a new coloring), has been considered, both to model radio network updates, and as a useful subroutine for coloring. Second, as it appears that general graphs and bounded-degree graphs do not model real networks very well (with, respectively, pathological worst-case topologies and too strong assumptions), coloring has been studied in more specific graph classes. In this paper, we study the intersection of these two directions: distributed recoloring in two relevant graph classes, interval and chordal graphs. More formally, the question of recoloring a graph is as follows: we are given a network, an input coloring α and a target coloring β, and we want to find a schedule of colorings to reach β starting from α. In a distributed setting, the schedule needs to be found within the LOCAL model, where nodes communicate with their direct neighbors synchronously. The question we want to answer is: how many rounds of communication {are} needed to produce a schedule, and what is the length of this schedule? In the case of interval and chordal graphs, we prove that, if we have less than 2ω colors, ω being the size of the largest clique, extra colors will be needed in the intermediate colorings. For interval graphs, we produce a schedule after O(poly(Δ)log*n) rounds of communication, and for chordal graphs, we need O(ω²Δ²log n) rounds to get one. Our techniques also improve classic coloring algorithms. Namely, we get ω+1-colorings of interval graphs in O(ωlog*n) rounds and of chordal graphs in O(ωlog n) rounds, which improves on previous known algorithms that use ω+2 colors for the same running times.
Cite as

Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich, and Mikaël Rabie. Distributed Recoloring of Interval and Chordal Graphs. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.19,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Heinrich, Marc and Rabie, Mika\"{e}l},
  title =	{{Distributed Recoloring of Interval and Chordal Graphs}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.19},
  URN =		{urn:nbn:de:0030-drops-157941},
  doi =		{10.4230/LIPIcs.OPODIS.2021.19},
  annote =	{Keywords: Distributed coloring, distributed recoloring, interval graphs, chordal graphs, intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.22
Local Certification of Graph Decompositions and Applications to Minor-Free Classes

Authors: Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph G belongs to a given graph class 𝒢. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this work, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds using a new proof technique.
Cite as

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.OPODIS.2021.22,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o},
  title =	{{Local Certification of Graph Decompositions and Applications to Minor-Free Classes}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.22},
  URN =		{urn:nbn:de:0030-drops-157970},
  doi =		{10.4230/LIPIcs.OPODIS.2021.22},
  annote =	{Keywords: Local certification, proof-labeling schemes, locally checkable proofs, graph decompositions, minor-free graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.8
(Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes

Authors: Gabriel Bathie, Nicolas Bousquet, and Théo Pierron

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
In a (parameterized) graph edge modification problem, we are given a graph G, an integer k and a (usually well-structured) class of graphs 𝒢, and ask whether it is possible to transform G into a graph G' ∈ 𝒢 by adding and/or removing at most k edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a 2k kernel [Cao and Chen, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size O(k/log k). We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH.
Cite as

Gabriel Bathie, Nicolas Bousquet, and Théo Pierron. (Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bathie_et_al:LIPIcs.IPEC.2021.8,
  author =	{Bathie, Gabriel and Bousquet, Nicolas and Pierron, Th\'{e}o},
  title =	{{(Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.8},
  URN =		{urn:nbn:de:0030-drops-153918},
  doi =		{10.4230/LIPIcs.IPEC.2021.8},
  annote =	{Keywords: kernelization, graph editing, split graphs, (sub)linear kernels}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2021.29
PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters

Authors: Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
This document describes our exact Cluster Editing solver, PaSTEC, which got the third place in the 2021 PACE Challenge.
Cite as

Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 29:1-29:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.IPEC.2021.29,
  author =	{Bartier, Valentin and Bathie, Gabriel and Bousquet, Nicolas and Heinrich, Marc and Pierron, Th\'{e}o and Prieto, Ulysse},
  title =	{{PACE Solver Description: PaSTEC - PAths, Stars and Twins to Edit Towards Clusters}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{29:1--29:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.29},
  URN =		{urn:nbn:de:0030-drops-154129},
  doi =		{10.4230/LIPIcs.IPEC.2021.29},
  annote =	{Keywords: cluster editing, exact algorithm, star packing, twins}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2021.33
PACE Solver Description: μSolver - Heuristic Track

Authors: Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
This document describes our heuristic Cluster Editing solver, μSolver, which got the third place in the 2021 PACE Challenge. We present the local search and kernelization techniques for Cluster Editing that are implemented in the solver.
Cite as

Valentin Bartier, Gabriel Bathie, Nicolas Bousquet, Marc Heinrich, Théo Pierron, and Ulysse Prieto. PACE Solver Description: μSolver - Heuristic Track. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 33:1-33:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.IPEC.2021.33,
  author =	{Bartier, Valentin and Bathie, Gabriel and Bousquet, Nicolas and Heinrich, Marc and Pierron, Th\'{e}o and Prieto, Ulysse},
  title =	{{PACE Solver Description: \muSolver - Heuristic Track}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{33:1--33:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.33},
  URN =		{urn:nbn:de:0030-drops-154161},
  doi =		{10.4230/LIPIcs.IPEC.2021.33},
  annote =	{Keywords: kernelization, graph editing, clustering, local search}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.49
Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes

Authors: Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph G belongs to a given graph class 𝒢. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this paper, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds with a new simple proof technique.
Cite as

Nicolas Bousquet, Laurent Feuilloley, and Théo Pierron. Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 49:1-49:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.DISC.2021.49,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Pierron, Th\'{e}o},
  title =	{{Brief Announcement: Local Certification of Graph Decompositions and Applications to Minor-Free Classes}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{49:1--49:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.49},
  URN =		{urn:nbn:de:0030-drops-148515},
  doi =		{10.4230/LIPIcs.DISC.2021.49},
  annote =	{Keywords: Local certification, proof-labeling schemes, locally checkable proofs, graph decompositions, minor-free graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.37
Linear Transformations Between Dominating Sets in the TAR-Model

Authors: Nicolas Bousquet, Alice Joffard, and Paul Ouvrard

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Given a graph G and an integer k, a token addition and removal (TAR for short) reconfiguration sequence between two dominating sets D_s and D_t of size at most k is a sequence S = ⟨ D₀ = D_s, D₁ …, D_𝓁 = D_t ⟩ of dominating sets of G such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than k. We first improve a result of Haas and Seyffarth [R. Haas and K. Seyffarth, 2017], by showing that if k = Γ(G)+α(G)-1 (where Γ(G) is the maximum size of a minimal dominating set and α(G) the maximum size of an independent set), then there exists a linear TAR reconfiguration sequence between any pair of dominating sets. We then improve these results on several graph classes by showing that the same holds for K_𝓁-minor free graph as long as k ≥ Γ(G)+O(𝓁 √(log 𝓁)) and for planar graphs whenever k ≥ Γ(G)+3. Finally, we show that if k = Γ(G)+tw(G)+1, then there also exists a linear transformation between any pair of dominating sets.
Cite as

Nicolas Bousquet, Alice Joffard, and Paul Ouvrard. Linear Transformations Between Dominating Sets in the TAR-Model. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ISAAC.2020.37,
  author =	{Bousquet, Nicolas and Joffard, Alice and Ouvrard, Paul},
  title =	{{Linear Transformations Between Dominating Sets in the TAR-Model}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.37},
  URN =		{urn:nbn:de:0030-drops-133812},
  doi =		{10.4230/LIPIcs.ISAAC.2020.37},
  annote =	{Keywords: reconfiguration, dominating sets, addition removal, connectivity, diameter, minor, treewidth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.44
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping

Authors: Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In the Token Jumping problem we are given a graph G = (V,E) and two independent sets S and T of G, each of size k ≥ 1. The goal is to determine whether there exists a sequence of k-sized independent sets in G, 〈S_0, S_1, ..., S_𝓁〉, such that for every i, |S_i| = k, S_i is an independent set, S = S_0, S_𝓁 = T, and |S_i Δ S_i+1| = 2. In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixed-parameter tractable on C_4-free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on {C_3,C_4}-free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant p ≥ 4, both problems are W[1]-hard on {C_4, ..., C_p}-free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.
Cite as

Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, and Amer E. Mouawad. On Girth and the Parameterized Complexity of Token Sliding and Token Jumping. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 44:1-44:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bartier_et_al:LIPIcs.ISAAC.2020.44,
  author =	{Bartier, Valentin and Bousquet, Nicolas and Dallard, Cl\'{e}ment and Lomer, Kyle and Mouawad, Amer E.},
  title =	{{On Girth and the Parameterized Complexity of Token Sliding and Token Jumping}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{44:1--44:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.44},
  URN =		{urn:nbn:de:0030-drops-133886},
  doi =		{10.4230/LIPIcs.ISAAC.2020.44},
  annote =	{Keywords: Combinatorial reconfiguration, Independent Set, Token Jumping, Token Sliding, Parameterized Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.24
Reconfiguration of Spanning Trees with Many or Few Leaves

Authors: Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Let G be a graph and T₁,T₂ be two spanning trees of G. We say that T₁ can be transformed into T₂ via an edge flip if there exist two edges e ∈ T₁ and f in T₂ such that T₂ = (T₁⧵e) ∪ f. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed in [Takehiro Ito et al., 2011]. We investigate the problem of determining, given two spanning trees T₁,T₂ with an additional property Π, if there exists an edge flip transformation from T₁ to T₂ keeping property Π all along. First we show that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at most k (for any fixed k ≥ 3) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at least k leaves (where k is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when k = n-2.
Cite as

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of Spanning Trees with Many or Few Leaves. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ESA.2020.24,
  author =	{Bousquet, Nicolas and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and Ouvrard, Paul and Suzuki, Akira and Wasa, Kunihiro},
  title =	{{Reconfiguration of Spanning Trees with Many or Few Leaves}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.24},
  URN =		{urn:nbn:de:0030-drops-128909},
  doi =		{10.4230/LIPIcs.ESA.2020.24},
  annote =	{Keywords: combinatorial reconfiguration, spanning trees, PSPACE, polynomial-time algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.49
When Maximum Stable Set Can Be Solved in FPT Time

Authors: Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, and Rémi Watrigant

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Maximum Independent Set (MIS for short) is in general graphs the paradigmatic W[1]-hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restricted to structured graph classes such as, for instance, perfect graphs (which includes bipartite graphs, chordal graphs, co-graphs, etc.) or claw-free graphs. In this paper, we introduce some variants of co-graphs with parameterized noise, that is, graphs that can be made into disjoint unions or complete sums by the removal of a certain number of vertices and the addition/deletion of a certain number of edges per incident vertex, both controlled by the parameter. We give a series of FPT Turing-reductions on these classes and use them to make some progress on the parameterized complexity of MIS in H-free graphs. We show that for every fixed t >=slant 1, MIS is FPT in P(1,t,t,t)-free graphs, where P(1,t,t,t) is the graph obtained by substituting all the vertices of a four-vertex path but one end of the path by cliques of size t. We also provide randomized FPT algorithms in dart-free graphs and in cricket-free graphs. This settles the FPT/W[1]-hard dichotomy for five-vertex graphs H.
Cite as

Édouard Bonnet, Nicolas Bousquet, Stéphan Thomassé, and Rémi Watrigant. When Maximum Stable Set Can Be Solved in FPT Time. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ISAAC.2019.49,
  author =	{Bonnet, \'{E}douard and Bousquet, Nicolas and Thomass\'{e}, St\'{e}phan and Watrigant, R\'{e}mi},
  title =	{{When Maximum Stable Set Can Be Solved in FPT Time}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.49},
  URN =		{urn:nbn:de:0030-drops-115458},
  doi =		{10.4230/LIPIcs.ISAAC.2019.49},
  annote =	{Keywords: Parameterized Algorithms, Independent Set, H-Free Graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.24
Linear Transformations Between Colorings in Chordal Graphs

Authors: Nicolas Bousquet and Valentin Bartier

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Let k and d be such that k >= d+2. Consider two k-colorings of a d-degenerate graph G. Can we transform one into the other by recoloring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. If k=d+2, we know that there exists graphs for which a quadratic number of recolorings is needed. And when k=2d+2, there always exists a linear transformation. In this paper, we prove that, as long as k >= d+4, there exists a transformation of length at most f(Delta) * n between any pair of k-colorings of chordal graphs (where Delta denotes the maximum degree of the graph). The proof is constructive and provides a linear time algorithm that, given two k-colorings c_1,c_2 computes a linear transformation between c_1 and c_2.
Cite as

Nicolas Bousquet and Valentin Bartier. Linear Transformations Between Colorings in Chordal Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ESA.2019.24,
  author =	{Bousquet, Nicolas and Bartier, Valentin},
  title =	{{Linear Transformations Between Colorings in Chordal Graphs}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.24},
  URN =		{urn:nbn:de:0030-drops-111459},
  doi =		{10.4230/LIPIcs.ESA.2019.24},
  annote =	{Keywords: graph recoloring, chordal graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.80
The Perfect Matching Reconfiguration Problem

Authors: Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.
Cite as

Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa. The Perfect Matching Reconfiguration Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.MFCS.2019.80,
  author =	{Bonamy, Marthe and Bousquet, Nicolas and Heinrich, Marc and Ito, Takehiro and Kobayashi, Yusuke and Mary, Arnaud and M\"{u}hlenthaler, Moritz and Wasa, Kunihiro},
  title =	{{The Perfect Matching Reconfiguration Problem}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.80},
  URN =		{urn:nbn:de:0030-drops-110248},
  doi =		{10.4230/LIPIcs.MFCS.2019.80},
  annote =	{Keywords: Combinatorial Reconfiguration, Graph Algorithms, Perfect Matching}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.17
Parameterized Complexity of Independent Set in H-Free Graphs

Authors: Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs H, we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and W[1]-hard cases. We first show that MIS remains W[1]-hard in graphs forbidding simultaneously K_{1, 4}, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning C_4-free graphs. Then we extend the polynomial algorithm of Alekseev when H is a disjoint union of edges to an FPT algorithm when H is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of iterative expansion accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called iterative compression. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs H.
Cite as

Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2018.17,
  author =	{Bonnet, \'{E}douard and Bousquet, Nicolas and Charbit, Pierre and Thomass\'{e}, St\'{e}phan and Watrigant, R\'{e}mi},
  title =	{{Parameterized Complexity of Independent Set in H-Free Graphs}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.17},
  URN =		{urn:nbn:de:0030-drops-102183},
  doi =		{10.4230/LIPIcs.IPEC.2018.17},
  annote =	{Keywords: Parameterized Algorithms, Independent Set, H-Free Graphs}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2013.3
Graph coloring, communication complexity and the stubborn problem (Invited Talk)

Authors: Nicolas Bousquet, Aurélie Lagoutte, and Thomassé Stéphan

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We discuss three equivalent forms of the same problem arising in communication complexity, constraint satisfaction problems, and graph coloring. Some partial results are discussed.
Cite as

Nicolas Bousquet, Aurélie Lagoutte, and Thomassé Stéphan. Graph coloring, communication complexity and the stubborn problem (Invited Talk). In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 3-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2013.3,
  author =	{Bousquet, Nicolas and Lagoutte, Aur\'{e}lie and St\'{e}phan, Thomass\'{e}},
  title =	{{Graph coloring, communication complexity and the stubborn problem}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{3--4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.3},
  URN =		{urn:nbn:de:0030-drops-39158},
  doi =		{10.4230/LIPIcs.STACS.2013.3},
  annote =	{Keywords: stubborn problem, graph coloring, Clique-Stable set separation, Alon-Saks-Seymour conjecture, bipartite packing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1824
A Polynomial Kernel for Multicut in Trees

Authors: Nicolas Bousquet, Jean Daligault, Stephan Thomasse, and Anders Yeo

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
The {\sc Multicut In Trees} problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer $k$, whether there exists a set of $k$ edges cutting all the requests. This problem was shown to be FPT by Guo and Niedermeyer (2005). They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows (2006). We show that {\sc Multicut In Trees} has a polynomial kernel.
Cite as

Nicolas Bousquet, Jean Daligault, Stephan Thomasse, and Anders Yeo. A Polynomial Kernel for Multicut in Trees. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 183-194, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2009.1824,
  author =	{Bousquet, Nicolas and Daligault, Jean and Thomasse, Stephan and Yeo, Anders},
  title =	{{A Polynomial Kernel for Multicut in Trees}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{183--194},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1824},
  URN =		{urn:nbn:de:0030-drops-18247},
  doi =		{10.4230/LIPIcs.STACS.2009.1824},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact